/**
 * Copyright 2014 The FROG Brigade
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package net.frogbrigade.bufonidae.util.hash;

/**
 * Austin Applebyが考案したMurmurHashアルゴリズムを利用するハッシュ関数です。
 * <p>
 * MurmurHashには次の制約があります。
 * <ol>
 * <li>インクリメンタルには動作しません。</li>
 * <li>リトルエンディアンとビックエンディアン環境では、異なる結果を返します。</li>
 * </ol>
 * <p>
 * 仕様の詳細は<a href="https://sites.google.com/site/murmurhash">MurmurHash Google
 * Sites</a>を参照してください。
 * 
 * @author nobuyuki sekimori
 * @see <a href="https://sites.google.com/site/murmurhash">MurmurHash Google
 *      Sites</a>
 * @since 1.0.0
 * @version 1.0.0
 */
public class MurmurHash
{
    private static final int DEFAULT_SEED = 0x9747b28c;

    /**
     * オブジェクトを生成します。
     */
    private MurmurHash()
    {
    }

    /**
     * 指定したデータのハッシュを生成します。
     * 
     * @param data
     *            ハッシュを生成するデータです。
     * @return ハッシュです。
     */
    public static int hash(byte[] data)
    {
        return MurmurHash.hash(data, data.length, MurmurHash.DEFAULT_SEED);
    }

    /**
     * 指定したシードを利用して指定したデータのハッシュを生成します。
     * 
     * @param data
     *            ハッシュを生成するデータです。
     * @param seed
     *            ハッシュの生成に利用するシードです。
     * @return ハッシュです。
     */
    public static int hash(byte[] data, int seed)
    {
        return MurmurHash.hash(data, data.length, seed);
    }

    /**
     * 指定したシードを利用して指定した長さのデータのハッシュを生成します。
     * 
     * @param data
     *            ハッシュを生成するデータです。
     * @param length
     *            ハッシュを生成するデータの長さです。
     * @param seed
     *            ハッシュの生成に利用するシードです。
     * @return ハッシュです。
     */
    public static int hash(byte[] data, int length, int seed)
    {
        int multiplier = 0x5bd1e995;
        int rotator = 24;
        int hash = seed ^ length;
        int readSize = length / 4;

        for (int i = 0; i < readSize; i++)
        {
            int offset = i * 4;
            int tmpHash = ((data[offset + 0] & 0xff) << 8 * 0) + ((data[offset + 1] & 0xff) << 8 * 1) + ((data[offset + 2] & 0xff) << 8 * 2)
                          + ((data[offset + 3] & 0xff) << 8 * 3);
            tmpHash *= multiplier;
            tmpHash ^= tmpHash >>> rotator;
            tmpHash *= multiplier;
            hash *= multiplier;
            hash ^= tmpHash;
        }

        int restSize = length % 4;

        switch (restSize)
        {
            case 3:
                hash ^= (data[(length & ~3) + 2] & 0xff) << 8 * 2;
            case 2:
                hash ^= (data[(length & ~3) + 1] & 0xff) << 8 * 1;
            case 1:
                hash ^= (data[(length & ~3) + 0] & 0xff) << 8 * 0;
                hash *= multiplier;
        }

        hash ^= hash >>> 13;
        hash *= multiplier;
        hash ^= hash >>> 15;

        return hash;
    }
}